package mianshi;

/**
 * description:
 * author:张腾
 * date:2021-07-18
 */

import niuke.ListNode;

/**
 * 编写一个函数，检查输入的链表是否是回文的。
 */
public class _02_06 {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast.next!=null&&fast.next.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode nHead = slow.next;
        slow.next = null;
        ListNode rHead = reverse(nHead);

        while (head!=null && rHead!=null){
            if (head.val!=rHead.val) return false;
            head = head.next;
            rHead = rHead.next;
        }

        return true;
    }

    public ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while (cur!=null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
